package main

import "fmt"

//写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
//F(0) = 0F(1= 1
//F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
//斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
//答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
//示例 1：
//输入：n = 2
//输出：1
//示例 2：
//输入：n = 5
//输出：5
//提示：
//0 <= n <= 100


//计算取模的原因

//在某些算法题里不要求解答者考虑程序中超出存储范围的数值该如何保存，但使用的数据又可能会溢出，所以允许用ans%mod来代替ans。
//作为mod的值有几个要求：mod要尽可能大，确保程序中可能的计算结果对该值取模后在数据类型的表示范围内。
//例如，a和b都是32位int类型的值，（a+b）的值取模后要在32位int类型表示的范围之内。如果mod值太小，比如极端点说，mod=1，则起不到足够的将ans缩小的作用。
//mod应该是一个质数，防止ans取模后等于0。例如：（9*5）%15 = 0。综上可知要选择一个32int表示范围内尽可能大的质数。
//1e9+7 = 1000000007 是32位int型数据能表示的范围内较大的几个质数之一。容易被记住也是使用该值的一个原因。
//
//func fib(n int) int {
//	if n==0 {
//		return 0
//	}
//	if n ==1 {
//		return 1
//	}
//	return fib(n-1)%1000000007 +fib(n-2)%1000000007
//}
func fib(n int ) int {
	a:=0
	b:=1
	sum:=1
	for i:=0;i<n-1;i++ { // i=1 计算的是 f(1)+f(0)也就是f(2);i =n -1计算的 f(n)也就是所需的结果
		sum=(a+b)%1000000007  // 187
		a=b
		b=sum
	}
	if n==0 {
		return 0
	}
	return sum
}
func main(){
   fmt.Println(fib(1))
}